SPLZ: An Efficient Algorithm for Single Source Shortest Path Problem Using Compression Method

摘要

Efficient solution of the single source shortest path (SSSP) problem on roadnetworks is an important requirement for numerous real-world applications. Thispaper introduces an algorithm for the SSSP problem using compression method.Owning to precomputing and storing all-pairs shortest path (APSP), the processof solving SSSP problem is a simple lookup of a little data from precomputedAPSP and decompression. APSP without compression needs at least 1TB memory fora road network with one million vertices. Our algorithm can compress such anAPSP into several GB, and ensure a good performance of decompression. In ourexperiment on a dataset about Northwest USA (with 1.2 millions vertices), ourmethod can achieve about three orders of magnitude faster than Dijkstraalgorithm based on binary heap.